package com.midea.tensort;

/**
 * @description：
 * @author: wangwl23
 * @create: 2021-03-09 11:09
 *
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{12,4,9,9,6,1};
        /*int[] bubble = bubble(arr);
        for (int t: bubble) {
            System.out.println(t);
        }*/
        int[] select = bucketSort(arr);
        for (int s: select) {
            System.out.println(s);
        }
    }

    //冒泡排序，外层循环控制次数，冒泡排序lenth-1次
    private static int[]  bubble(int[] arr) {
        for(int i = 1;i<arr.length;i++){
            //内层控制相邻下标元素循环做比较
            for (int j=0;j<arr.length-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

    //选择排序，循环挑出最小值，最后一个不用挑。
    private static  int[] select(int[] arr){
        int n = arr.length;
        for (int i =0;i<n-1;i++){
            int min = i;
            //挑出来的最小值，左边是已排好序的，右边是无序的
            for(int j = i+1;j<n;j++){
                if(arr[min]>arr[j]){
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }

    //桶排序
    private static int[] bucketSort(int[] arr){
        int[] newArr = new int[arr.length];
        if (arr==null || arr.length<2){
            return newArr;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0;i<arr.length;i++){
            max = Math.max(arr[i],max);
        }
        int[] bucket = new int[max+1];
        for (int i = 0;i<arr.length;i++){
            bucket[arr[i]]++;
        }
        int i = 0;
        for(int j=0;j<bucket.length;j++){
            while (bucket[j]-->0){
                newArr[i++]=j;
            }
        }
        return newArr;
    }
}
